package Leetcode第二期;

/**
 * @author : K k
 * @date : 12:25 2020/10/2
 * 给定一个非负整数数组，你最初位于数组的第一个位置。
 * <p>
 * 数组中的每个元素代表你在该位置可以跳跃的最大长度。
 * <p>
 * 判断你是否能够到达最后一个位置。
 * <p>
 * 示例 1:
 * <p>
 * 输入: [2,3,1,1,4]
 * 输出: true
 * 解释: 我们可以先跳 1 步，从位置 0 到达 位置 1, 然后再从位置 1 跳 3 步到达最后一个位置。
 * 示例 2:
 * <p>
 * 输入: [3,2,1,0,4]
 * 输出: false
 * 解释: 无论怎样，你总会到达索引为 3 的位置。但该位置的最大跳跃长度是 0 ， 所以你永远不可能到达最后一个位置。
 */
public class 跳跃游戏_55 {

    //思路1：动态规划 找出每个位置是否能走到能满足条件的位置（从后往前）
    public boolean canJump(int[] nums) {
        int n = nums.length;
        if (n <= 1) {
            return true;
        }
        boolean[] dp = new boolean[n - 1];
        int i = n - 2;
        if (nums[i] >= 1) {
            dp[i] = true;
        }
        i--;
        while (i >= 0) {
            boolean flag=false;
            for(int j=i+1;j<=i+Math.min(nums[i],n-2-i);j++){
                if (dp[j] == true) {
                    flag=true;
                }
            }
            dp[i] = flag || nums[i]>n-2-i;
            i--;
        }
        return dp[0];
    }

    //思路2：动态规划，找出每个位置最大的最大步长
    public boolean canJumpA(int[] nums) {
        int n=nums.length;
        int mostLocation=0;
        for (int i=0;i<n;i++){
            if (i<=mostLocation){
                mostLocation=Math.max(mostLocation,i+nums[i]);
                if (mostLocation>=n-1){
                    return true;
                }
            }
        }
        return false;
    }

    public static void main(String[] args) {
        跳跃游戏_55 x = new 跳跃游戏_55();
        System.out.println(x.canJump(new int[]{3, 2, 1, 0, 4}));
    }
}
